package 算法.leetcode.labuladong.数组和链表;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author lchenglong
 * @date 2022/6/21
 */
public class 带限制的子序列和 {
    class Solution {
        public int constrainedSubsetSum(int[] nums, int k) {
            int n = nums.length;
            // 单调队列
            Deque<Integer> window = new ArrayDeque<>() ;
            // 存储动态规划结果的数组
            int[] dp = new int[n];
            // 我们直接放入 f[0] 的值，防止处理边界情况
            dp[0] = nums[0];
            // 一开始唯一的 j 为 0
            window.addFirst(0);
            int ans = nums[0];
            for (int i=1;i<n;i++) {
                // 队首j与i相差超过K,不满足条件了 弹出
                while (!window.isEmpty()&&i-window.getFirst()>k){
                    window.removeFirst();
                }
                // 此时队首的 j 即为最优的 j 值
                dp[i] = Math.max(dp[window.peekFirst()],0) + nums[i];
                ans = Math.max(dp[i],ans);
                // 维护队列的单调性
                while (!window.isEmpty()&&dp[i]>=dp[window.peekLast()]){
                    window.removeLast();
                }
                // 将 i 作为之后的新 j 值放入队尾
                window.addLast(i);
            }
            return ans;
        }


    }
}
